//2789.合并后数组中的最大元素
//https://leetcode.cn/problems/largest-element-in-an-array-after-merge-operations/description/?envType=daily-question&envId=2024-03-14
class Solution {
public:
    long long maxArrayValue(vector<int>& nums) {
        int n = nums.size();
        //正向遍历，当nums[i+1]>前缀数组和sum 则sum调整为nums[i+1]
        //但是这样有一个问题，就是nums[0]<nums[1]时 sum会不断调整 变成了选择数组中最大的数
        //此时我们可以反向遍历 记录nums[i] 如果>sum则调整为nums[i] 否则+=
        if (n == 1) return nums[0];
        long long sum = nums.back();
        for (int i = n-2; i >= 0; --i) sum = nums[i]<=sum?sum+nums[i]:nums[i];
        return sum;
    }
};